语法分析由解析器完成，接下来我们将实现解析器。它的基础是前面小节中的语法和词法分析器。解析过程的结果是一个动态数据结构，称为抽象语法树(AST)。AST是输入的一个非常紧凑的表示，非常适合语义分析。

首先，将实现解析器，再了解AST的解析过程。

\mySubsubsection{2.4.1.}{手写解析器}

解析器的接口在头文件Parser.h中定义，以一些include声明开始:

\begin{cpp}
#ifndef PARSER_H
#define PARSER_H

#include "AST.h"
#include "Lexer.h"
#include "llvm/Support/raw_ostream.h"
\end{cpp}

AST.h头文件声明AST的接口，将在后面展示。LLVM的编码指南禁止使用<iostream>库，所以包含了等效LLVM功能的头文件。这里需要发出一个错误消息:

\begin{enumerate}
\item
Parser类首先声明一些私有成员:

\begin{cpp}
class Parser {
    Lexer &Lex;
    Token Tok;
    bool HasError;
\end{cpp}

Lex和Tok是前一节中类的实例。Tok存储下一个标记(预检)，Lex用于从输入中检索下一个标记。HasError标志表示是否检测到错误。

\item
有几个方法处理这个标记:

\begin{cpp}
    void error() {
        llvm::errs() << "Unexpected: " << Tok.getText()
        << "\n";
        HasError = true;
    }

    void advance() { Lex.next(Tok); }

    bool expect(Token::TokenKind Kind) {
        if (Tok.getKind() != Kind) {
            error();
            return true;
        }
        return false;
    }

    bool consume(Token::TokenKind Kind) {
        if (expect(Kind))
            return true;
        advance();
        return false;
    }
\end{cpp}

advance()从词法分析器检索下一个标记。Expect()测试预检是否具有预期的类型，否则发出错误消息。最后，若预检具有预期的类型，则consume()将检索下一个标记。若发出错误消息，则将HasError标志设置为true。

\item
对于语法的每个非终结符，声明一个解析规则的方法:

\begin{cpp}
    AST *parseCalc();
    Expr *parseExpr();
    Expr *parseTerm();
    Expr *parseFactor();
\end{cpp}

\begin{myNotic}{Note}
没有标识和编号的方法。这些规则只返回标记，并用相应的标记替换。
\end{myNotic}

\item
接下来是公共接口。构造函数初始化所有成员，并从词法分析器获取第一个标记:

\begin{cpp}
public:
    Parser(Lexer &Lex) : Lex(Lex), HasError(false) {
        advance();
    }
\end{cpp}

\item
需要一个函数来获取错误标志的值:

\begin{cpp}
    bool hasError() { return HasError; }
\end{cpp}

\item
最后，parse()方法是解析的主要入口:

\begin{cpp}
    AST *parse();
};

#endif
\end{cpp}

\end{enumerate}

\mySubsubsection{2.4.1.1}{解析器的实现}

让我们深入了解解析器的实现!

\begin{enumerate}
\item
Parser.cpp文件的实现中，以parse()开始:

\begin{cpp}
#include "Parser.h"

AST *Parser::parse() {
    AST *Res = parseCalc();
    expect(Token::eoi);
    return Res;
}
\end{cpp}

parse()的要点是使用了整个输入。还记得第一节中的解析示例中，添加了一个特殊符号来表示输入的结束吗?需要在这里进行检查。

\item
parseCalc()实现相应的规则。因为其他解析方法也遵循相同的模式，所以有必要仔细研究一下这个方法。回顾一下第一节的规则:

\begin{cpp}
calc : ("with" ident ("," ident)* ":")? expr ;
\end{cpp}

\item
该方法首先声明一些局部变量:

\begin{cpp}
AST *Parser::parseCalc() {
    Expr *E;
    llvm::SmallVector<llvm::StringRef, 8> Vars;
\end{cpp}

\item
第一个决定是是否必须解析可选组。组以with标记开始，将标记与以下值进行比较:

\begin{cpp}
if (Tok.is(Token::KW_with)) {
    advance();
\end{cpp}

\item
接下来，需要一个标识符:

\begin{cpp}
    if (expect(Token::ident))
        goto _error;
    Vars.push_back(Tok.getText());
    advance();
\end{cpp}

若标识符存在，则将其保存在Vars vector中。否则，就是一个语法错误，单独处理。

\item
接下来是一个重复组，解析了更多的标识符，并用逗号分隔:

\begin{cpp}
    while (Tok.is(Token::comma)) {
        advance();
        if (expect(Token::ident))
            goto _error;
        Vars.push_back(Tok.getText());
        advance();
    }
\end{cpp}

重复组以标记(，)开头，标记的测试成为while循环的条件，实现零或更多次的重复。循环内的标识符和以前一样进行处理。

\item
最后，可选组需要在末尾加一个冒号:

\begin{cpp}
    if (consume(Token::colon))
        goto _error;
}
\end{cpp}

\item
最后，必须解析expr规则:

\begin{cpp}
    E = parseExpr();
\end{cpp}

\item
有了这个调用，规则的解析就完成了。收集到的信息可以用于为该规则创建AST节点:

\begin{cpp}
    if (Vars.empty()) return E;
    else return new WithDecl(Vars, E);
\end{cpp}
\end{enumerate}

现在只缺少错误处理。检测语法错误很容易，但从中恢复却异常复杂。这里使用了一种简单的方法，称为恐慌模式。

恐慌模式下，标记会从标记流中删除，直到找到一个解析器可以使用它继续工作。大多数编程语言都有表示结束的符号，例如：C++中，a;(语句结束)或\}(语句块结束)。这样的标记是很好的候选对象。

另一方面，错误可能是正在寻找的符号丢失了，所以可能在解析器继续之前删除了许多标记。这并不像听起来那么糟糕，现在更重要的是编译器的速度。若出现错误，开发人员查看第一条错误消息，修复它，然后重新启动编译器。这与使用打孔卡完全不同，打孔卡非常重要的是获取尽可能多的错误消息，因为编译器的下一次运行可能要在第二天才可以进行。

\mySubsubsection{2.4.1.2}{错误处理}

这里没有使用一些标记来查找，而是使用了另一组标记。对于每个非终结符，在规则中都有一组标记可以跟随该非终结符:

\begin{enumerate}
\item
在calc中，只有输入的结尾跟在这个非终结符后面。实现很简单:

\begin{cpp}
_error:
    while (!Tok.is(Token::eoi))
        advance();
    return nullptr;
}
\end{cpp}

\item
其他解析方法的构造也类似。parseExpr()是对expr规则的翻译:

\begin{cpp}
Expr *Parser ::parseExpr() {
    Expr *Left = parseTerm() ;
    while (Tok.isOneOf(Token::plus, Token::minus)) {
        BinaryOp::Operator Op =
            Tok.is(Token::plus) ? BinaryOp::Plus :
                                  BinaryOp::Minus;
        advance();
        Expr *Right = parseTerm();
        Left = new BinaryOp(Op, Left, Right);
    }
    return Left;
}
\end{cpp}

规则中的重复组可转换为while循环，使用isOneOf()方法简化了对多个标记的检查。

\item
术语规则的编码看起来都一样:

\begin{cpp}
Expr *Parser::parseTerm() {
    Expr *Left = parseFactor();
    while (Tok.isOneOf(Token::star, Token::slash)) {
        BinaryOp::Operator Op =
            Tok.is(Token::star) ? BinaryOp::Mul :
                                  BinaryOp::Div;
        advance();
        Expr *Right = parseFactor();
        Left = new BinaryOp(Op, Left, Right);
    }
    return Left;
}
\end{cpp}

此方法与parseExpr()非常相似，有的读者可能想将它们合并为一个方法。在语法中，可以使用一个规则处理乘法和加性操作符。使用两个规则的优点是，操作符的优先级与求值的数学顺序非常吻合。若结合了这两个规则，需要在其他地方弄清楚求值顺序。

\item
最后，需要实现解析factor规则:

\begin{cpp}
Expr *Parser::parseFactor() {
    Expr *Res = nullptr;
    switch (Tok.getKind()) {
        case Token::number:
        Res = new Factor(Factor::Number, Tok.getText());
        advance(); break;
\end{cpp}

这里不使用if和else if语句链，而使用switch语句，因为每个选项都只以一个标记开头。一般来说，应该考虑喜欢使用哪种翻译模式。若以后需要更改解析方法，并不是每个方法都有不同的实现语法规则的方式，这就很方便修改了。

\item
若使用switch语句，错误处理将在默认情况下发生:

\begin{cpp}
    case Token::ident:
        Res = new Factor(Factor::Ident, Tok.getText());
        advance(); break;
    case Token::l_paren:
        advance();
        Res = parseExpr();
        if (!consume(Token::r_paren)) break;
    default:
        if (!Res) error();
\end{cpp}

由于失败，需要在这里避免发出错误消息。

\item
若括号表达式中存在语法错误，则已经发出错误消息。这个守卫可以防止第二个错误消息:

\begin{cpp}
        while (!Tok.isOneOf(Token::r_paren, Token::star,
                            Token::plus, Token::minus,
                            Token::slash, Token::eoi))
            advance();
    }
    return Res;
}
\end{cpp}

\end{enumerate}

这很简单，不是吗?记住使用的模式之后，根据语法规则编写解析器是一项乏味的工作。这种类型的解析器称为递归下降解析器。

\begin{myNotic}{并非所有语法都能用于构造递归下降解析器}
语法必须满足某些条件才能适合于构造递归下降解析器，这类语法称为LL(1)。事实上，能在网上能找到的大多数语法都不属于这类语法。大多数关于编译器结构理论的书籍都解释了这一点的原因。关于这个话题的经典书籍是所谓的“龙书”——《编译器:原则，技术和工具》，由Aho, Lam, Sethi和Ullman编写。
\end{myNotic}

\mySubsubsection{2.4.2.}{抽象语法树}

解析过程的结果是AST，AST是输入程序的另一种紧凑表示，捕获了基本信息。许多编程语言都有作为分隔符的符号，但这些符号没有进一步的含义。例如：在C++中，分号;表示单个语句的结束，这些信息对解析器很重要。当将语句转换为内存中的表示形式后，分号就不重要，可以删除了。

看一下示例表达式语言的第一条规则，with关键字、逗号(，)和冒号(:)对于程序的含义并不重要。重要的是声明的变量列表，可以在表达式中使用。结果是只需要几个类来记录信息:Factor保存一个数字或标识符，BinaryOp保存算术运算符和表达式的左右两边，WithDecl存储声明的变量和表达式的列表。AST和Expr仅用于创建公共类层次结构。

除了来自解析输入的信息外，还支持使用访问者模式对树进行遍历。这都在AST.h头文件中有所体现:

\begin{enumerate}
\item
开始于访问者接口:

\begin{cpp}
#ifndef AST_H
#define AST_H

#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"

class AST;
class Expr;
class Factor;
class BinaryOp;
class WithDecl;

class ASTVisitor {
    public:
    virtual void visit(AST &){};
    virtual void visit(Expr &){};
    virtual void visit(Factor &) = 0;
    virtual void visit(BinaryOp &) = 0;
    virtual void visit(WithDecl &) = 0;
};
\end{cpp}

访问者模式需要知道要访问的每个类。每个类也引用访问者，所以在文件的顶部声明所有类。请注意，AST和Expr的visit()方法有一个默认实现，但不做任何事情。

\item
AST类是层次结构的根:

\begin{cpp}
class AST {
public:
    virtual ~AST() {}
    virtual void accept(ASTVisitor &V) = 0;
};
\end{cpp}

\item
类似地，Expr是与表达式相关的AST类的根:

\begin{cpp}
class Expr : public AST {
public:
    Expr() {}
};
\end{cpp}

\item
Factor类存储一个数字或一个变量的名称:

\begin{cpp}
class Factor : public Expr {
public:
    enum ValueKind { Ident, Number };

private:
    ValueKind Kind;
    llvm::StringRef Val;

public:
    Factor(ValueKind Kind, llvm::StringRef Val)
        : Kind(Kind), Val(Val) {}
    ValueKind getKind() { return Kind; }
    llvm::StringRef getVal() { return Val; }
    virtual void accept(ASTVisitor &V) override {
        V.visit(*this);
    }
};
\end{cpp}

本例中，数字和变量的处理方式几乎相同，所以可以只创建一个AST节点类来表示。Kind成员实例代表两种情况中的哪一种。在更复杂的语言中，通常希望使用不同的AST类，例如：用于数字的NumberLiteral类和用于变量引用的VariableAccess类。

\item
BinaryOp类保存表达式求值所需的数据:

\begin{cpp}
class BinaryOp : public Expr {
public:
    enum Operator { Plus, Minus, Mul, Div };

private:
    Expr *Left;
    Expr *Right;
    Operator Op;

public:
    BinaryOp(Operator Op, Expr *L, Expr *R)
        : Op(Op), Left(L), Right(R) {}
    Expr *getLeft() { return Left; }
    Expr *getRight() { return Right; }
    Operator getOperator() { return Op; }
    virtual void accept(ASTVisitor &V) override {
        V.visit(*this);
    }
};
\end{cpp}

与解析器相反，BinaryOp类不区分乘法运算符和加法运算符。操作符的优先级在树结构中隐式可用。

\item
最后，WithDecl类存储了声明的变量和表达式:

\begin{cpp}
class WithDecl : public AST {
    using VarVector =
        llvm::SmallVector<llvm::StringRef, 8>;
    VarVector Vars;
    Expr *E;

public:
    WithDecl(llvm::SmallVector<llvm::StringRef, 8> Vars,
            Expr *E)
        : Vars(Vars), E(E) {}
    VarVector::const_iterator begin()
                                { return Vars.begin(); }
    VarVector::const_iterator end() { return Vars.end(); }
    Expr *getExpr() { return E; }
    virtual void accept(ASTVisitor &V) override {
        V.visit(*this);
    }
};
#endif
\end{cpp}

\end{enumerate}

AST是在解析过程中构造的。语义分析检查树是否符合语言的含义(例如，使用已声明的变量)，并可能对树进行扩充，树将用于代码生成。